package 牛客_面试必刷.Month07.day10;

public class 构建二叉树 {
    int index = 0;
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin){
        //根据中序遍历数组来构造数组
        return preorder(pre,vin,0,vin.length);
    }

    public TreeNode preorder(int[] pre,int[] vin,int left,int right){
        if(index == pre.length || right <= left) return null;
        int mid =  left;//准备遍历中序数组来找根节点
        while(mid < right){
            if(pre[index] == vin[mid]) break;
            mid++;
        }
        //注意，这里定义val值一定是根据前序数组来确定的
        int val = pre[index++];
        TreeNode root = new TreeNode(val);
        root.left = preorder(pre,vin,left,mid);
        root.right = preorder(pre,vin,mid + 1,right);
        return root;
    }
}
